package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

/**
 * Created with IntelliJ IDEA.
 * 1943. 描述绘画结果
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/2 13:29
 */
public class SplitPainting {

    public List<List<Long>> splitPainting(int[][] segments) {
        TreeSet<Integer> set = new TreeSet<>();
        int max = 0;
        for (int[] x : segments) {
            set.add(x[0]);
            set.add(x[1]);
            max = Math.max(max, x[1]);
        }
        long[] array = new long[max + 1];
        for (int[] x : segments) {
            array[x[0]] += x[2];
            array[x[1]] -= x[2];
        }
        for (int i = 1; i < max + 1; i++) {
            array[i] = array[i - 1] + array[i];
        }
        List<List<Long>> ans = new ArrayList<>();
        while (set.size() > 1) {
            List<Long> temp = new ArrayList<>();
            int l = set.pollFirst();
            int r = set.first();
            long value = array[l];
            if (value == 0) {
                continue;
            }
            temp.add((long) l);
            temp.add((long) r);
            temp.add(value);
            ans.add(temp);
        }
        return ans;
    }

}
